package class02;

/**
 * N:表示数据量
 * a:子问题调用了几次
 * b:子问题是主问题规模的占比的倒数
 * d:子问题操作的时间复杂度(除了递归之外的时间复杂度)
 * <p>
 * 递归复杂度: T(N) = a*T(N/b) + O(N^d)
 * 1): log_b a > d (以b为底, a的对数), 那么复杂度为 O(N^log_b a)
 * 1): log_b a < d (以b为底, a的对数), 那么复杂度为 O(N^d)
 * 1): log_b a == d (以b为底, a的对数), 那么复杂度为 O(N^d * log N)
 * <p>
 * a: leftMax rightMax 调用了两次, 那么 a=2
 * b: process(arr, L, mid) 取中点划分问题规模, 那么 b= 1 / (1/2) = 1 / 0.5 = 2
 * d: Math.max(leftMax, rightMax)时间复杂度为O(1), 那么 d=O(1)=O(N^0)
 * <p>
 * 那么: getMax 的 T(N)
 * T(N) = 2*T(N/2) + O(N^0)
 * 命中: log_b a > d , (log2 = 1) > 0
 * 复杂度为: O(N^log_b a) = O(N^1) = O(N)
 */
public class Code08_GetMax {

    // 求arr中的最大值
    public static int getMax(int[] arr) {
        return process(arr, 0, arr.length - 1);
    }

    // 使用递归方式(递归实际利用的是系统栈, 那么自己模拟压栈弹栈就可以将递归操作改为非递归操作)
    // 改为非递归可以稍微优化操作, 避免栈溢出(栈最大大小可调)
    // arr[L..R]范围上求最大值  L ... R   N
    public static int process(int[] arr, int L, int R) {
        if (L == R) { // arr[L..R]范围上只有一个数，直接返回，base case
            return arr[L];
        }
        int mid = L + ((R - L) >> 1); // 中点   	1
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

}
